{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Processing Time"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minProcessingTime"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #最小处理时间"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有 <code>n</code> 颗处理器，每颗处理器都有 <code>4</code> 个核心。现有 <code>n * 4</code> 个待执行任务，每个核心只执行 <strong>一个</strong> 任务。</p>\n",
    "\n",
    "<p>给你一个下标从 <strong>0</strong> 开始的整数数组 <code>processorTime</code> ，表示每颗处理器最早空闲时间。另给你一个下标从 <strong>0</strong> 开始的整数数组 <code>tasks</code> ，表示执行每个任务所需的时间。返回所有任务都执行完毕需要的 <strong>最小时间</strong> 。</p>\n",
    "\n",
    "<p>注意：每个核心独立执行任务。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>processorTime = [8,10], tasks = [2,2,3,1,8,7,4,5]\n",
    "<strong>输出：</strong>16\n",
    "<strong>解释：</strong>\n",
    "最优的方案是将下标为 4, 5, 6, 7 的任务分配给第一颗处理器（最早空闲时间 time = 8），下标为 0, 1, 2, 3 的任务分配给第二颗处理器（最早空闲时间 time = 10）。 \n",
    "第一颗处理器执行完所有任务需要花费的时间 = max(8 + 8, 8 + 7, 8 + 4, 8 + 5) = 16 。\n",
    "第二颗处理器执行完所有任务需要花费的时间 = max(10 + 2, 10 + 2, 10 + 3, 10 + 1) = 13 。\n",
    "因此，可以证明执行完所有任务需要花费的最小时间是 16 。</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>processorTime = [10,20], tasks = [2,3,1,2,5,8,4,3]\n",
    "<strong>输出：</strong>23\n",
    "<strong>解释：</strong>\n",
    "最优的方案是将下标为 1, 4, 5, 6 的任务分配给第一颗处理器（最早空闲时间 time = 10），下标为 0, 2, 3, 7 的任务分配给第二颗处理器（最早空闲时间 time = 20）。 \n",
    "第一颗处理器执行完所有任务需要花费的时间 = max(10 + 3, 10 + 5, 10 + 8, 10 + 4) = 18 。 \n",
    "第二颗处理器执行完所有任务需要花费的时间 = max(20 + 2, 20 + 1, 20 + 2, 20 + 3) = 23 。 \n",
    "因此，可以证明执行完所有任务需要花费的最小时间是 23 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n == processorTime.length &lt;= 25000</code></li>\n",
    "\t<li><code>1 &lt;= tasks.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= processorTime[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>1 &lt;= tasks[i] &lt;= 10<sup>9</sup></code></li>\n",
    "\t<li><code>tasks.length == 4 * n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-processing-time](https://leetcode.cn/problems/minimum-processing-time/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-processing-time](https://leetcode.cn/problems/minimum-processing-time/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[8,10]\\n[2,2,3,1,8,7,4,5]', '[10,20]\\n[2,3,1,2,5,8,4,3]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:\n",
    "        \n",
    "        ans = 0\n",
    "        tasks.sort()\n",
    "        processorTime.sort()\n",
    "        \n",
    "        for i in range(len(processorTime)):\n",
    "            \n",
    "            tmp = 0\n",
    "            for _ in range(4):\n",
    "                tmp = max(tmp, tasks.pop())\n",
    "            \n",
    "            ans = max(ans, processorTime[i] + tmp)\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:\n",
    "        processorTime.sort(reverse=True)\n",
    "        heapq.heapify(tasks)\n",
    "        end = -1\n",
    "        for b in processorTime:\n",
    "            for _ in range(4):\n",
    "                end = max(end, b + heapq.heappop(tasks))\n",
    "        return end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:\n",
    "        tasks.sort()\n",
    "        processorTime.sort()\n",
    "        r = 0\n",
    "        for t in processorTime:\n",
    "            for _ in range(4):\n",
    "                r = max(r, t + tasks.pop())\n",
    "        return r"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:\n",
    "        h = []\n",
    "        for p in processorTime:\n",
    "            h += [p] * 4\n",
    "        heapq.heapify(h)\n",
    "        tasks.sort()\n",
    "        ans = 0\n",
    "        while tasks:\n",
    "            t = heapq.heappop(h)\n",
    "            finish_time = t + tasks.pop()\n",
    "            # heapq.heappush(h, finish_time) # 注意题目要求：每个核心只执行 一个 任务。如果没有这个要求， 这个注释去掉就可以了\n",
    "            ans = max(ans, finish_time)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProcessingTime(self, p: List[int], t: List[int]) -> int:\n",
    "        p.sort()\n",
    "        t.sort(reverse=True)\n",
    "        ans = 0\n",
    "        while p: ans = max(ans,p.pop()+max(t.pop(),t.pop(),t.pop(),t.pop()))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:\n",
    "        processorTime.sort()\n",
    "        tasks.sort(reverse=True)\n",
    "        return max(p + t for p, t in zip(processorTime, tasks[::4]))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:\n",
    "        n = len(processorTime)\n",
    "        processorTime.sort()\n",
    "        tasks.sort(reverse = True)\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            start = i*4\n",
    "            for j in range(start,start+4):\n",
    "                res = max(res,tasks[j]+processorTime[i]) \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:\n",
    "        processorTime = sorted(processorTime)\n",
    "        tasks = sorted(tasks, reverse=True)\n",
    "        n: int = len(processorTime)\n",
    "        ans: int = 0\n",
    "        for i in range(n):\n",
    "            # 机器等待时间\n",
    "            p = processorTime[i]\n",
    "            # 任务处理时间\n",
    "            t = tasks[4 * i]\n",
    "            ans = max(ans, p + t)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minProcessingTime(self, processorTime: List[int], tasks: List[int]) -> int:\n",
    "        #贪心 + 排序\n",
    "        l1 = []\n",
    "        p = -1\n",
    "        processorTime.sort()\n",
    "        processorTime = processorTime[::-1]\n",
    "        tasks.sort()\n",
    "        for i in range (len(tasks)):\n",
    "            if i % 4 == 0:\n",
    "                p += 1\n",
    "            x = tasks[i] + processorTime[p]\n",
    "            l1.append(x)\n",
    "        return max(l1)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
